2.7 KB · ⇊ 2 parts · ⤓ Micron 2.7 KB · ⤓ HTML 19.6 KB

top

Given two graphs G {\displaystyle G} and G ′ {\displaystyle G'} , the maximum common edge subgraph problem is the problem of finding a graph H {\displaystyle H} with as many edges as possible which is isomorphic to both a subgraph of G {\displaystyle G} and a subgraph of G ′ {\displaystyle G'} .

The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph H {\displaystyle H} is isomorphic to a subgraph of another graph G {\displaystyle G} if and only if the maximum common edge subgraph of G {\displaystyle G} and H {\displaystyle H} has the same number of edges as H {\displaystyle H} . The problem is APX-hard, unless the two input graphs G {\displaystyle G} and G ′ {\displaystyle G'} are required to have the same number of vertices.cite-ref-1[1]

• See also

• References

• Maximum common subgraph isomorphism problem

• Subgraph isomorphism problem

• Induced subgraph isomorphism problem

cite-note-11. ↑ citerefbahiensemanicpivade-souza2012Bahiense, L.; Manic, G.; Piva, B.; de Souza, C. C. (2012), "The maximum common edge subgraph problem: A polyhedral investigation", Discrete Applied Mathematics, 160 (18): 2523–2541, doi:10.1016/j.dam.2012.01.026.